﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

//最简单的是先序遍历，在里面记录一下

class MyBst
{
    TreeNode root;
    Dictionary<TreeNode, int> nodeNum;// 记录以node为根结点的子树的结点数

    public MyBst(TreeNode root)
    {
        this.root = root;
        this.nodeNum = new Dictionary<TreeNode, int>();
        CountNodeNum(root);
    }

    // 返回二叉搜索树中第k小的元素
    public int KthSmallest(int k)
    {
        TreeNode node = root;
        while (node != null)
        {
            int left = GetNodeNum(node.left);
            if (left < k - 1)//左孩子的数量小于k，说明k在右边
            {
                node = node.right;
                k -= left + 1;
            }
            else if (left == k - 1)//左孩子的数量等于k，说明k就是根节点
            {
                break;
            }
            else
            {
                node = node.left;
            }
        }
        return node.val;
    }

    // 统计以node为根结点的子树的结点数
    private int CountNodeNum(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        nodeNum.Add(node, 1 + CountNodeNum(node.left) + CountNodeNum(node.right));
        return nodeNum[node];
    }

    // 获取以node为根结点的子树的结点数
    private int GetNodeNum(TreeNode node)
    {
        return node != null && nodeNum.ContainsKey(node) ? nodeNum[node] : 0;
    }
}



class Sol230
{
    public int KthSmallest2(TreeNode root,int k)
    {


        if (root == null) return 0;
        int rank = 1;
        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (root != null || stack.Count > 0)
        {


            while (root != null)
            {

                stack.Push(root);
                root = root.left;

            }
            root = stack.Pop();
            if (rank == k)
            {
                return root.val;
            }
            else
            {
                rank++;
            }


            root = root.right;
        }


        return rank;
    }

    //记录子树的结点数    如果你需要频繁地查找第 k 小的值，你将如何优化算法？


    public int KthSmallest(TreeNode root, int k)
    {
        MyBst myBst=new MyBst(root);
      return   myBst.KthSmallest(k);





    }



}

class Program230
{
    static void Main230(string[] args)
    {
        string s = "3 1 2 4";
        string[] chars = s.Split(" ");
        int[] nums = new int[chars.Length];
        for (int i = 0; i < chars.Length; i++)
        {
            nums[i] = int.Parse(chars[i]);
        }

        int[] inOrder = { 1,2,3,4 };
       
        Solution105 solution105 = new Solution105();



        TreeNode root = solution105.BuildTree(nums, inOrder);

        //solution105.levelOrder(root);

        Sol230 sol = new Sol230();
        int res= sol.KthSmallest(root,1);
        Console.WriteLine(res);
    }
}